package 二分查找;

public class LeetCode74_搜索二维矩阵 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = searchMatrixFirstColumn(matrix,target);
        if(rowIndex < 0) {
            return false;
        }
        return searchMatrixRow(matrix[rowIndex],target);
    }

    private boolean searchMatrixRow(int[] colIndex, int target) {
        int row = 0;
        int col = colIndex.length - 1;
        while (row <= col) {
            int mid = (col-row) / 2 + row;
            if(colIndex[mid] == target) {
                return true;
            }else if(colIndex[mid] > target) {
                col = mid - 1;
            }else {
                row = mid + 1;
            }
        }
        return false;
    }

    private int searchMatrixFirstColumn(int[][] matrix, int target) {
        int low = -1;
        int high = matrix.length-1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if(matrix[mid][0] <= target) {
                low = mid;
            }else {
                high = mid - 1;
            }
        }
        return low;
    }
}
